import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Heap {

    private int[] elem;
    private int usedSize;

    public Heap(){
        this.elem = new int[10];
    }

    public void initHeap(int[] array){
        for (int i = 0; i < array.length; i++){
            elem[i] = array[i];
            usedSize++;
        }
    }

    //建堆（大根堆）
    public void createHeap(){
        int parent = ((usedSize - 1) - 1) / 2;
        for(; parent >= 0; parent--){
            //调用向下调整建堆
            shiftDown(parent, usedSize);
        }
    }

    /**
     * 向下调整建堆
     * @param parent
     * @param size
     */
    public void shiftDown(int parent, int size){
        //先将左孩子定义为child，因为parent可能没有右孩子
        //并且默认左孩子是孩子中的最大
        int child = 2 * parent + 1;

        while(child < size){
            //如果有右孩子，找到两个孩子中较大的那个
            if(child + 1 < size && elem[child] < elem[child + 1]){
                child++;
            }
            //如果孩子大于父亲，交换孩子和父亲
            if(elem[child] > elem[parent]){
                swap(child, parent);
                //将孩子赋值给父亲，继续向下调整
                parent = child;
                child = 2 * parent + 1;
            }else {
                //如果父亲大于孩子，则退出
                break;
            }
        }
    }

    /**
     * 交换算法，这里的i，j 是数组中的下标
     * @param i
     * @param j
     */
    public void swap(int i, int j){
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

    /**
     * 向上调整
     * @param child
     */
    public void shiftUp(int child){
        int parent = (child - 1) / 2;
        while(child > 0){
            if(elem[child] > elem[parent]){
                swap(child, parent);
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }

    public void offer(int val){
        if(isFull()){
            this.elem = Arrays.copyOf(this.elem, usedSize * 2);
        }
        this.elem[usedSize] = val;
        //向上调整
        shiftUp(usedSize);
        usedSize++;
    }

    public int poll(){
        int tmp = elem[0];
        swap(0, usedSize - 1);
        usedSize--;
        shiftDown(0, usedSize);
        return tmp;
    }

    public boolean isFull(){
        return usedSize == elem.length;
    }

    public int peek(){
        return elem[0];
    }

    /**
     * TopK问题
     * @param arr
     * @param k
     * @return
     */
    public int[] smallestK1(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k <= 0){
            return ret;
        }
        // PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>(){

        //     public int compare(Integer o1, Integer o2){
        //         return o2.compareTo(o1);
        //     }
        // });
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for(int i = 0; i < arr.length; i++){
            priorityQueue.offer(arr[i]);
        }
        for(int i = 0; i < k; i++){
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }

    public int[] smallestK2(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k <= 0){
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>(){

            public int compare(Integer o1, Integer o2){
                return o2.compareTo(o1);
            }
        });
        for(int i = 0; i < k; i++){
            priorityQueue.offer(arr[i]);
        }
        for(int i = k; i < arr.length; i++){
            if(arr[i] < priorityQueue.peek()){
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for(int i = 0; i < k; i++){
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }

}
